package com.easy.carl.algorithm.tree;

import com.easy.leetcode.tree.TreeNode;

public class HasPathSum112 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root==null){
            return false;
        }
        return help(root,targetSum- root.val);
    }

    public boolean help(TreeNode current,int count){
        //递归终止条件
        //当前节点是叶子节点
       if (current.left==null&&current.right==null&&count==0){
           return true;
       }
       //叶子节点，count 不是0，返回false
        if (current.left==null&&current.right==null){
            return false;
        }
        //左节点不为空时才继续递归
        if (current.left!=null){
            //回溯
            count-=current.left.val;
            //只有返回值为true时才返回，不能直接 return (help(current.left,count)
            //这样会造成不能回溯问题
            if (help(current.left,count)){
                return true;
            }
            count+=current.left.val;
        }
        if (current.right!=null){
            count-=current.right.val;
            if (help(current.right,count)) {
                return true;
            }
            count+=current.right.val;
        }
        return false;
    }
}
